import java.util.*;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.HashMap;




public class Test {

    class Node{
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {

        HashMap<Node,Node> map=new HashMap<>();

        Node cur=head;
        while (cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }

        cur=head;

        while (cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
    public List<String> topKFrequent(String[] words , int k){
        HashMap<String,Integer> map=new HashMap<>();

        for (String word : words) {
            if (map.get(word)==null){
                map.put(word,1);
            } else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }

        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if (minHeap.size()<k){
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> top=minHeap.peek();
                if (top.getValue().compareTo(entry.getValue())<0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if (top.getValue().compareTo(entry.getValue())==0){
                    if (top.getKey().compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        ArrayList<String> list=new ArrayList<>();

        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp=minHeap.poll();
            list.add(tmp.getKey());
        }

        Collections.reverse(list);

        return list;
    }

    public static void main(String[] args) {

    }
}
